package twoPointers;

import java.util.Arrays;

//https://leetcode.cn/problems/valid-triangle-number/
public class l_611 {
    public int triangleNumber(int[] nums) {
        int left, right, ans = 0, n = nums.length;
        Arrays.sort(nums);

        //如果a <= b <= c 那么 a + b > c 一次判断就说明abc可构成三角形
        //枚举c, c左边的区间用双指针判断有多少a和b可构成三角形
        for(int i = n - 1; i >= 2; --i) {
            left = 0;
            right = i - 1;
            while(left != right) {
                if(nums[left] + nums[right] > nums[i]) {
                    ans += right - left;
                    --right;
                } else ++left;
            }
        }
        return ans;
    }
}
